#include <bits/stdc++.h>

using namespace std;

const int maxn=100005;

namespace HLD{
    int n,en,curpos;
    int v[maxn*2],g[maxn],nxt[2*maxn];
    int pos[maxn],w[maxn],top[maxn],fa[maxn],dep[maxn],siz[maxn],son[maxn],ws[maxn];

    inline void init(){
        memset(g,-1,sizeof g);
        siz[0]=0;fa[1]=0;top[1]=1;dep[1]=0;
    }
    inline void addEdge(const int &x,const int &y){
        v[en]=y;nxt[en]=g[x];g[x]=en++;
        v[en]=x;nxt[en]=g[y];g[y]=en++;
    }
    void dfs(int p){
        siz[p]=1;son[p]=0;
        for(int j=g[p];~j;j=nxt[j]){
            const int &tar=v[j];
            if(tar==fa[p]) continue;
            fa[tar]=p;dep[tar]=dep[p]+1;
            dfs(tar);
            siz[p]+=siz[tar];
            if(siz[tar]>siz[son[p]]) son[p]=tar;
        }
    }
    void decomp(int p){
        pos[p]=++curpos;ws[curpos]=w[p];
        if(son[p]) {top[son[p]]=p;decomp(son[p]);}
        for(int j=g[p];~j;j=nxt[j]){
            const int &tar=v[j];
            if(tar==fa[p]||tar==son[p]) continue;
            top[tar]=tar;decomp(tar);
        }
    }
    inline void build(int p,int l,int r){

    }
}

namespace BCC{
    int en,n;
    int belong[maxn],dfn[maxn],low[maxn];
    int v[maxn*2],sta[maxn],g[maxn],nxt[maxn*2],w[maxn];
    int clock,bcc,head;
    bool iscut[maxn];

    void init(){
        memset(g,-1,sizeof(g));
        memset(dfn,0,sizeof dfn);
        memset(iscur,0,sizeof iscur);
        memset(w,0x3f,sizeof w);
    }
    inline void addEdge(const int &x,const int &y){
        v[en]=y;nxt[en]=g[x];g[x]=en++;
        v[en]=x;nxt[en]=g[y];g[y]=en++;
    }
    void dfs(int p,int fa){
        low[p]=dfn[p]=++clock;
        stack[head++]=p;
        int child=0;
        int &lowp=low[p];
        for(int j=g[p];~j;j=nxt[j]){
            const int &tar=v[j];
            if(tar==fa) continue;
            child++;
            if(dfn[tar]) lowp=min(low[p],low[tar]);
            else{
                dfs(tar,p);
                if(low[tar]>=p){
                    iscut[p]=1;
                    bcc++;
                    while(sta[--head]!=p) belong[p]=bcc;
                    head++;
                }
            }
        }
        if(fa<1&&child==1) iscur[p]=0;
    }
    void buildGraph(){
        for(int i=1;i<=n;i++){
            if(iscut[i]){
                belong[i]=++bcc;
                for(int j=g[p];~j;j=nxt[j]) addEdge(bcc,belong[v[j]]);
            }
            HLD::w[belong[i]]=min(HLD::w[belong[i]],w[i]);
            HLD::n=bcc;
        }
    }
}

